|
|
Hlavní nabídka Prohlížení IS/STAG
Nalezené předměty, počet: 1
Stránkování výsledků vyhledávání
Nalezeno 1 záznamů
Export do Xls
Informace o předmětu
KIV / IDT
:
Popis předmětu
Pracoviště / Zkratka
|
KIV
/
IDT
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Implementace datových struktur
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
2
[HOD/TYD]
Cvičení
2
[HOD/TYD]
|
Zápočet před zkouškou
|
Ano
|
Zápočet před zkouškou
|
Ano
|
Automatické uznávání zápočtu před zkouškou
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
Čeština
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Letní semestr
|
199 / -
|
6 / -
|
2 / -
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
0 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Letní semestr
|
Vyučovaný semestr
|
Letní semestr
|
Minimum (B + C) studentů
|
nestanoveno
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
Čeština
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
0
|
Hodnotící stupnice |
1|2|3|4 |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ano
|
Profilující předmět |
Ano
|
Základní teoretický předmět |
Ano
|
Hodnotící stupnice |
1|2|3|4 |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
Žádný
|
Vyloučené předměty
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
KIV/PPA nebo KIV/PPA-E
|
Předměty,které předmět podmiňuje
|
Nejsou definovány
|
Graf četnosti udělených hodnocení studentům napříč roky:
Obrázek PNG
,
XLS
|
Cíle předmětu (anotace):
|
Cílem předmětu je demonstrovat způsoby implementace základních abstraktních datových typů, tj. zásobníku, fronty, seznamu, tabulky, prioritní fronty, stromů, grafů a dalších. Klíčovým nástrojem je koncept výpočetní složitosti, který bude podrobně formálně zaveden a diskutován ve všech praktických případech. Předmět je nadstavbou pro KIV/ADS, dává studentům vhled do způsobu jak jsou základní abstraktní datové typy běžně implementovány a jaké mají konkrétní implementace vliv na jejich vlastnosti.
|
Požadavky na studenta
|
Vyřešení domácích zadání, průběžný test. Získání zápočtu do konce června.
Z důvodu průběžné aktualizace předmětu je pro získání zápočtu při opakovaném zapsání předmětu (viz SZŘ čl. 24 odst. 3) nutné souhlasné vyjádření garanta předmětu.
Upozornění:
Termíny a forma ověřování splnění požadavků mohou být upraveny s ohledem na opatření vyhlášená v souvislosti s vývojem epidemiologické situace v ČR.
|
Obsah
|
1. Problém, algoritmus, program. Program a programovací jazyk. Vykonání programu. Objekt, třída.
2. Generické programování, koncept rozhraní, polymorfismus. Rekurzivní programy.
3. Výpočetní složitost, O, Omega a Theta množiny.
4. Řazení. InsertSort, ShellSort, QuickSort, MergeSort.
5. Abstraktní datové typy. Kolekce. Zásobník - implementace polem, implementace spojovou strukturou.
6. Odstranění rekurze uživatelským zásobníkem. Fronta - možné implementace.
7. Seznam, iterátor, možné implementace.
8. Tabulka s přímým adresováním. Rozptylové tabulky. Rozptylová funkce.
9. Stromy, binární vyhledávací stromy, vyvážené stromy.
10. Graf, implementace seznamem sousednosti, implementace maticí sousednosti. Prohledávání do šířky.
11. Topologické řazení, prohledávání do hloubky.
12. Prioritní fronta, halda.
13. Formalizace a klasifikace problémů. Třídy problémů P, NP a NP-C
|
Aktivity
|
|
Studijní opory
|
Pro předmět existuje systém opor v LMS Moodle se všemi podstatnými informacemi a materiály
|
Garanti a vyučující
|
-
Garanti:
Doc. Ing. Libor Váša, Ph.D. ,
-
Přednášející:
Doc. Ing. Libor Váša, Ph.D. (100%),
-
Cvičící:
Ing. Milan Hotovec (100%),
Ing. Zuzana Káčereková (100%),
Ing. Alex König (100%),
Ing. Michal Nykl, Ph.D. (100%),
Ing. Jana Varnušková, Ph.D. (100%),
Doc. Ing. Libor Váša, Ph.D. (100%),
Ing. Natálie Vítová, M.Sc. (100%),
|
Literatura
|
|
Časová náročnost
|
Všechny formy studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Kontaktní výuka
|
52
|
Vypracování seminární práce v bakalářském studijním programu [5-40]
|
39
|
Příprava na zkoušku [10-60]
|
26
|
Příprava na souhrnný test [6-30]
|
13
|
Celkem
|
130
|
|
Předpoklady
|
Odborné znalosti - pro úspěšné zvládnutí předmětu se předpokládá, že je student před zahájením výuky schopen: |
orientovat se v primitivních datových typech používaných pro reprezentaci celých čísel, čísel s plovoucí desetinnou čárkou a znaků v počítači |
orientovat se v základních imperativních řídících strukturách |
popsat principy programování v imperativních jazycích, zejména základních řídících struktur |
prokazovat znalosti základních pojmů a metod z matematiky |
Odborné dovednosti - pro úspěšné zvládnutí předmětu se předpokládá, že student před zahájením výuky dokáže: |
na základní uživatelské úrovni používat některé z běžných vývojových prostředí |
provádět základní matematická odvození a výpočty |
vytvářet jednoduché programy v imperativním programovacím jazyce |
Obecné způsobilosti - před zahájením studia předmětu je student schopen: |
bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
bc. studium: efektivně využívá různé strategie učení k získání a zpracování poznatků a informací, hledá a rozvíjí účinné postupy ve svém učení, |
bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
bc. studium: rozpozná problém, objasní jeho podstatu, rozčlení ho na části, |
bc. studium: vytváří hypotézy, navrhuje postupné kroky, zvažuje využití různých postupů při řešení problému nebo ověřování hypotézy, |
|
Výsledky učení
|
Odborné znalosti - po absolvování předmětu prokazuje student znalosti: |
interpretovat výroky o složitosti algoritmů a složitostních třídách O, Theta a Omega |
interpretovat výroky o složitosti problémů, porozumět výrokům o třídách složitosti P, NP a NP-C |
popsat způsob vykonání programuv počítači, zejména z hlediska alokace paměti v zásobníku a na hromadě a vytváření zásobníkových rámců |
samostatně určit výpočetní složitost operací nad konkrétními implementacemi abstraktních datových typů, zejména u standardních implementací |
vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
Odborné dovednosti - po absolvování předmětu prokazuje student dovednosti: |
analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
implementovat programy využívající základní principy objektového programování |
implementovat složitější algoritmy zpracovávající dynamické datové struktury |
implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
vytvářet složitější datové struktury podle konkrétních zadání, zejména s ohledem na volbu vhodné implementace abstraktního datového typu |
vytvářet implementace abstraktních datových typů přizpůsobené konkrétním úlohám |
Obecné způsobilosti - po absolvování předmětu je student schopen: |
bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
|
Hodnoticí metody
|
Odborné znalosti - odborné znalosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Písemná zkouška, |
Kombinovaná zkouška, |
Test, |
Průběžné hodnocení, |
Seminární práce, |
Odborné dovednosti - odborné dovednosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Písemná zkouška, |
Kombinovaná zkouška, |
Test, |
Průběžné hodnocení, |
Seminární práce, |
Obecné způsobilosti - obecné způsobilosti dosažené studiem předmětu jsou ověřovány hodnoticími metodami: |
Ústní zkouška, |
Písemná zkouška, |
Kombinovaná zkouška, |
Test, |
Seminární práce, |
Průběžné hodnocení, |
|
Vyučovací metody
|
Odborné znalosti - pro dosažení odborných znalostí jsou užívány vyučovací metody: |
Přednáška založená na výkladu, |
Přednáška s demonstrací, |
Přednáška s diskusí, |
Cvičení (praktické činnosti), |
E-learning, |
Samostudium, |
Kooperativní výuka, |
Řešení problémů, |
Samostatná práce studentů, |
Odborné dovednosti - pro dosažení odborných dovedností jsou užívány vyučovací metody: |
Přednáška založená na výkladu, |
Přednáška s demonstrací, |
Přednáška s diskusí, |
Cvičení (praktické činnosti), |
E-learning, |
Řešení problémů, |
Kooperativní výuka, |
Samostudium, |
Samostatná práce studentů, |
Obecné způsobilosti - pro dosažení obecných způsobilostí jsou užívány vyučovací metody: |
Přednáška založená na výkladu, |
Přednáška s demonstrací, |
Cvičení (praktické činnosti), |
E-learning, |
Řešení problémů, |
Samostudium, |
Samostatná práce studentů, |
|
|
|
|